#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //贪心算法--不一定正确
    int ans1(vector<int>& coins, int amount){
        sort(coins.begin(), coins.end());
        reverse(coins.begin(), coins.end());
        int len = coins.size();
        
        int counts = 0, i = 0;
        while(amount > 0){
            if(amount >= coins[i]){
                amount = amount - coins[i];
                counts++;
            }else{
                i++;
                if(i == len){
                    break;
                }
            }
        }
        if(amount != 0){
            return -1;
        }
        return counts;
    }

    int ans2(vector<int>& coins, int amount){
        vector<int> dp(amount+1, INT16_MAX);
        dp[0] = 0;
        for(int i = 1; i != amount+1; i++){
            for(int j = 0; j != (int)coins.size(); j++){
                if(coins[j] <= i){
                    dp[i] = min(dp[i], dp[i-coins[j]]+1);
                }
            }
        }
        if(dp[amount] > amount){
            return -1;
        }else{
            return dp[amount];
        }
    }
};

void test1(){
    Solution s;
    vector<int> coins = {1, 2, 5};
    int amount = 11;

    // int ret = s.ans1(coins, amount);
    int ret = s.ans2(coins, amount);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> coins = {2};
    int amount = 3;

    // int ret = s.ans1(coins, amount);
    int ret = s.ans2(coins, amount);
    cout << ret << endl;
}

void test3(){
    Solution s;
    vector<int> coins = {186,419,83,408};
    int amount = 6249;

    // int ret = s.ans1(coins, amount);
    int ret = s.ans2(coins, amount);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}